//直接插入排序
void InsertSort(vector<int>& v)
{
    int n =  v.size();
    for(int i = 0;i<n-1;i++) //注意:i的范围是[0,n-2]
    {
        //思想:将x插入到[0,end]的有效区间
        int end = i;
        int x = v[end+1];
        while(end >= 0) //找到合适的位置插入
        {
            if(v[end] > x)
            {
                v[end+1] = v[end]; //当前元素往后挪
                end--;//下一轮判断,前一个数和x比较
            }
            else 
                break;//找到插入位置了
        }
        v[end + 1] = x;//插入到此时的end位置的后面
    }
}

//希尔排序
void ShellSort(vector<int>& v)
{
    int n =  v.size();
    int gap = n; //gap为几就分为几组, 预排序
    while(gap > 1)
    {
        //目的是为了保证最后能让gap为1,进行直接插入排序
        gap = gap / 3 + 1; //或者:gap = gap / 2 
        //写法1:一锅炖
        for(int i = 0 ;i < n - gap;i++) //注意:i的范围！ 否则end+gap会越界
        {
            int end  = i;//end的范围:[0,n- gap -1]
            int x = v[end + gap];//i的范围:[gap,n - 1]
            while(end >= 0)
            {
                if(v[end] > x)
                {
                    v[end + gap] = v[end];//把a[end]往后移动,以gap为间隔的为一组,所以移动到a[end+gap]位置
                    end -= gap;//下一轮循环,以gap为间隔的为一组,前一个数(end-gap位置对应的值)和x比较
                }
                else 
                    break;
            }
            v[end + gap] = x;//以gap为间隔的为一组,把x放在end + gap位置
        }
    }
}

//写法2：
void ShellSort(vector<int>& v)
{
    int n =  v.size();
    int gap = n; //gap为几就分为几组, 预排序
    while(gap > 1)
    {
        //目的是为了保证最后能让gap为1,进行直接插入排序
        gap = gap / 3 + 1; //或者:gap = gap / 2 

        //gap组,每组单独排序
        for(int j = 0;j<gap;j++)
        {
            for(int i = j ;i < n - gap;i+=gap) //注意:i的初始值！！和变动范围 i+=gap
            {
                int end  = i;//end的范围:[0,n- gap -1]
                int x = v[end + gap];//i的范围:[gap,n - 1]
                while(end >= 0)
                {
                    if(v[end] > x)
                    {
                        v[end + gap] = v[end];//把a[end]往后移动,以gap为间隔的为一组,所以移动到a[end+gap]位置
                        end -= gap;//下一轮循环,以gap为间隔的为一组,前一个数(end-gap位置对应的值)和x比较
                    }
                    else 
                        break;
                }
                v[end + gap] = x;//以gap为间隔的为一组,把x放在end + gap位置
            }
        }


    }
}


//选择排序
void SelectSort(vector<int>& v)
{
    int n = v.size();
    int end = n-1;
    while(end > 0)//当区间只有一个元素就不需要选了所以循环条件为：end > 0
    {
        int maxIndex = 0;
        //从[0,end]区间选取一个数放到end位置
        for(int i = 0;i<=end;i++)
        {
            if(v[i] > v[maxIndex])  //更新最大值所在位置的下标
                maxIndex = i;
        }
        ::swap(v[end],v[maxIndex]);
        end--;//缩小区间
    }
}

//写法2：
void SelectSort(vector<int>& v)
{
    int n = v.size();
    int begin = 0,end = n -1;
    while(begin < end)
    {
        //在[begin,end]区间找出最大最小的位置
        int maxIndex = begin,minIndex = begin;
        for(int i = begin;i<=end;i++)
        {
            if(v[i] > v[maxIndex]) maxIndex = i;
            if(v[i] < v[minIndex]) minIndex = i;
        }
        ::swap(v[begin],v[minIndex]);//最小值放到begin位置

        //坑点：如果begin和maxIndex一样
        //因为下面一步begin位置和值已经和minIndex位置交换了,所以就导致了minIndex位置放的才是最大值了
        //所以需要特判一下,如果begin和maxIndex相同,那么经过上面一步交换之后,minIndex位置放的才是最大值
        if(begin == maxIndex) 
            maxIndex = minIndex;
        ::swap(v[end],v[maxIndex]);//最大值放到end位置

        begin++,end--;//缩小区间
    }
}

//堆排序
//排升序 建大堆
void AdjustDown(vector<int>& v,int parent,int n) //从哪个位置向下调整,堆中有效元素个数
{
    int child = parent * 2 + 1; //左孩子
    while(child < n) //最坏情况：调整到叶子节点
    {
        if(child + 1 < n && v[child + 1] > v[child]) //选出较大的孩子
            child += 1;
        if(v[child] > v[parent])
        {
            ::swap(v[child],v[parent]); 
            //向下迭代
            parent = child;
            child = parent*2+1;
        }
        else 
            break; //已经是大堆了
    }
}

void HeapSort(vector<int>& v)
{
    int n = v.size();
    //1.从最后一个节点(下标:n-1)的父节点((child - 1 )/ 2)开始建堆(向下调整建堆)
    for(int i = (n - 1 - 1 )/ 2;i>=0;i--)
        AdjustDown(v,i,n);
    //2.调堆
    int end = n-1;//认为是堆中有效元素的个数 & 当前堆顶元素应该交换之后放的位置
    while(end > 0)
    {
        ::swap(v[end],v[0]);
        AdjustDown(v,0,end);//从根节点开始向下调整,认为堆中元素个数为end个
        end--;
    }
}

//向上调整建堆：
//排升序 建大堆
void AdjustUp(vector<int>& v,int child)
{
    int parent = (child - 1) / 2;
    while(parent >= 0) //最坏情况：调整到根节点(根节点可能也要和其孩子交换,所以条件是>=)
    {
        if(v[child] > v[parent])
        {
            ::swap(v[child],v[parent]);
            //向上迭代
            child = parent;
            parent = (child - 1
                     ) / 2;
        }
        else 
            break;//堆已经构建好了
    }
}

//建堆
//1.第一个元素认为是堆，然后从第二个元素开始每个元素都进行向上调整
for(int i = 1; i<n;i++)
    AdjustUp(v,i);


//冒泡排序
void BubbleSort(vector<int>& v)
{
    int n = v.size();
    //每一趟可以确定一个元素到准确位置,n个元素只需要进行n-1趟
    for(int i = 0;i<n-1;i++)
    {
        bool flag = true;//是否已经有序
        //每一趟都可以少比较一个已经确定好的数
        for(int j = 0;j<n - 1 - i;j++) //注意:j<n-1-i
        {
            if(v[j] >v[j+1])
            {
                ::swap(v[j],v[j+1]);
                flag = false;
            }
        }
        if(flag) break;//如果没有进入交换，就是说明已经有序了
    }
}



//hoare版本
int process(vector<int>& v,int left,int right)
{
    int keyi = left;//左边的作为key  那么右边先走
    while(left < right)
    {
        //右往左走 找严格小的
        while(left < right && v[right] >= v[keyi])
            right--;
        //左往右走 找严格大的
        while(left < right && v[left] <= v[keyi])
            left++;

        if(left < right) ::swap(v[right],v[left]);
    }
    ::swap(v[left],v[keyi]); 
    return left;
}
void QucikSort(vector<int>& v,int left,int right)
{
    if(left >= right) return ;
    ::swap(v[left],v[left + rand() % (right - left + 1)]);//取左边位置作为基准值 ==> 本质是随机选key 
    int keyi = process(v,left,right);
    //[left,keyi-1] keyi[keyi+1,right]
    QucikSort(v,left,keyi-1);
    QucikSort(v,keyi+1,right);
}

//挖坑法
int process(vector<int>& v,int left,int right)
{
    int keyi = v[left];//左边的作为key  那么右边先走
    int pivot = left;//坑位
    while(left < right)
    {
        //右往左走 找严格小的
        while(left < right && v[right] >= keyi)
            right--;
        ::swap(v[right],v[pivot]);
        pivot = right;//更新坑位

        //左往右走 找严格大的
        while(left < right && v[left] <= keyi)
            left++;
        ::swap(v[left],v[pivot]);
        pivot = left;//更新坑位
    }
    v[pivot] = keyi;
    return pivot;
}
void QucikSort(vector<int>& v,int left,int right)
{
    if(left >= right) return ;
    ::swap(v[left],v[left + rand() % (right - left + 1)]);//取左边位置作为基准值 ==> 本质是随机选key 
    int keyi = process(v,left,right);
    //[left,keyi-1] keyi[keyi+1,right]
    QucikSort(v,left,keyi-1);
    QucikSort(v,keyi+1,right);
}

//两路划分
int process(vector<int>& v,int left,int right)
{
    int lessEqual = left - 1;//表示<=基准值的区域
    int cur = left;
    //遍历[left,right-1]区间,以右边作为基准值
    while(cur < right)
    {
        if(v[cur] <= v[right])
            swap(v[++lessEqual],v[cur]);
        cur++; //不管怎么样,cur都要往右走
    }
    //[left,lessEqual)表示<=基准值的区域
    ::swap(v[++lessEqual],v[right]);
    return lessEqual;
}
void QucikSort(vector<int>& v,int left,int right)
{
    if(left >= right) return ;
    ::swap(v[right],v[left + rand() % (right - left + 1)]); //取右边位置作为基准值 ==> 本质是随机选key 
    int keyi = process(v,left,right);
    //[left,keyi-1] keyi[keyi+1,right]
    QucikSort(v,left,keyi-1);
    QucikSort(v,keyi+1,right);
}

//三路划分
//作用：选取[left,right]的一个数为基准值
//然后把这个区间内的元素划分为: 左边<pivot  中间=pivot 右边>pivot
int* process(vector<int>& v,int left,int right,int pivot)
{
    int less = left;// <pivot的区域 [left,less)
    int more = right;// >pivot的区域 (more,right]
    int cur = left;
    //从left位置开始往后走，直到和more相遇,more位置的值也需要考察
    while(cur <= more)
    {
        if(v[cur] > pivot)
            ::swap(v[more--],v[cur]); //当前数换到大于区域当中,还要继续考察换过来的这个数
        else if(v[cur] < pivot)
            ::swap(v[less++],v[cur++]);//当前数换到小于区域当中,然后cur往后走
        else
            cur++;
    }
    //[left,less) [less,more] (more,right]
    return new int[2]{less,more};
}
void QucikSort(vector<int>& v,int left,int right)
{
    if(left >= right) return ;
    ::swap(v[right],v[left + rand() % (right - left + 1)]);
    int* equal = process(v,left,right,v[right]);
    //[left,equal[0]-1] [euqal[0],equal[1]] [euqal[1]+1,right]
    QucikSort(v,left,equal[0]-1);
    QucikSort(v,equal[1]+1,right);
}

//小区间优化
void InsertSort_QuickSort(vector<int>& v,int left,int right)
{
    for(int i = left;i<right;i++) 
    {
        int end = i;//end的范围:[left,right-1]
        int x = v[end+1];//将x插入到[0,end]的有序区间
        while(end >= left) //注意：这里最多移动到left！！！并不是0
        {
            if(v[end] > x)
            {
                v[end+1] = v[end];
                end -= 1;
            }
            else
                break;
        }
        v[end+1] = x;
    }
}   
//作用：选取[left,right]的一个数为基准值
//然后把这个区间内的元素划分为: 左边<pivot  中间=pivot 右边>pivot
int* PartSort(vector<int>& v,int left,int right,int pivot)
{
    int less = left;// <pivot的区域 [left,less)
    int more = right;// >pivot的区域 (more,right]
    int cur = left;
    //从left位置开始往后走，直到和more相遇,more位置的值也需要考察
    while(cur <= more)
    {
        if(v[cur] > pivot)
            ::swap(v[more--],v[cur]); //当前数换到大于区域当中,还要继续考察换过来的这个数
        else if(v[cur] < pivot)
            ::swap(v[less++],v[cur++]);//当前数换到小于区域当中,然后cur往后走
        else
            cur++;
    }
    //[left,less) [less,more] (more,right]
    return new int[2]{less,more};
}
void QuickSort(vector<int>& v,int left,int right)
{
    if(left >= right)
        return ;
    if(right - left +1 < 10)
    {
        InsertSort_QuickSort(v,left,right);
    }
    else
    {
        //结合随机选数
        ::swap(v[right],v[left + rand() %(right - left + 1)]);
        //PartSort以最右边的值为划分值,返回的是 等于arr[right]的区域的范围 [equalArea[0],equalArea[1]]
        int* equalArea = PartSort(v,left,right,v[right]);
        //[left,equalArea[0]-1] [equalArea[1] + 1,right]
        QuickSort(v,left,equalArea[0]-1);
        QuickSort(v,equalArea[1]+1,right);
    }
}
//快排非递归 -能过oj
void QuickSortNonR(vector<int>& v,int left,int right)
{
    if(left >= right) return ;
    stack<int> st;//存储要排序的区间
    //注意：栈的特性为后进先出
    st.push(right);
    st.push(left);
    while(!st.empty()) //还有区间要排序
    {
        int begin = st.top();//左端点
        st.pop();
        int end = st.top();//右端点
        st.pop();
        if(end - begin + 1 < 10)
        {
            InsertSort_QuickSort(v,begin,end);
            continue;
        }

        ::swap(v[end],v[begin + rand() % (end - begin + 1)]);
        int* equalArea = PartSort(v,begin,end,v[end]);
        //[left,equalArea[0]-1] [equalArea[1] + 1,right]
        if(right > equalArea[1] + 1)
        {
            QuickSortNonR(v,equalArea[1]+1,right); //仍然需要递归
        }
        if(equalArea[0]-1 > left)
        {
            QuickSortNonR(v,left,equalArea[0]-1);
        }

    }
}

//不能过oj-全是重复数据时超时
void Insert_Quick(vector<int>& v,int left,int right)
{
    for(int i = left;i<right;i++) //i < right!!!!
    {
        int end = i;
        int x = v[end+1];
        while(end  >= left) //坑！！ end最多移动到left位置
        {
            if(v[end] > x)
                v[end + 1 ]  = v[end],end--;
            else 
                break;
        }
        v[end + 1] = x;
    }
}
void QuickSortNonR(vector<int>& v,int left,int right)
{
    if(left>=right) return ;
    stack<int> st;
    st.push(left);
    st.push(right);
    while(!st.empty())
    {
        //栈的特性：后进先出,所以先拿到右端点
        int end = st.top();
        st.pop();
        int begin = st.top();
        st.pop();
        if(end - begin + 1 < 10)
        {
            Insert_Quick(v,begin,end);
            continue;
        }
        ::swap(v[begin],v[begin + rand() % (end - begin + 1)]);//左边作为基准值
        int keyi = PartSort(v,begin,end);
        //[begin,keyi-1] key [keyi+1,end]
        if(keyi-1 > begin)
        {
            st.push(begin);
            st.push(keyi-1);
        }
        if(end > keyi+1)
        {
            st.push(keyi+1);
            st.push(end);
        }
    }
}

//归并
void MergeSort(vector<int>& v,int left,int right,vector<int>& tmp)
{
    if(left >= right)  //数组只有一个元素/区间不合法就结束
        return ;
    //求中间值：left + (right - left) / 2 或者  (left + right) >> 1
    int mid = (left + right) / 2;
    MergeSort(v,left,mid,tmp);//左区间[left,mid]排成有序
    MergeSort(v,mid+1,right,tmp);//右区间[mid+1,right]排成有序

    //左右区间进行归并
    int begin1 = left,end1 = mid,begin2 = mid+1,end2 = right;
    int index = left;//拷贝到临时数组的哪个位置
    while(begin1 <= end1 && begin2 <= end2)
    {
        //排升序,谁小拷贝谁
        if(v[begin1] > v[begin2])
            tmp[index++] = v[begin2++];
        else  //相同的时候,先拷贝左边,再拷贝右边==>稳定
            tmp[index++] = v[begin1++];
    }
    //某个区间可能还未拷贝完,继续拷贝
    while(begin1 <= end1) tmp[index++] = v[begin1++];
    while(begin2 <= end2) tmp[index++] = v[begin2++];
    //将临时数组的数据重新拷贝回去原数组,注意起始位置为left！！ [left,right]区间
    for(int i = left;i<=right;i++)
        v[i] = tmp[i];
}


//计数排序
//绝对映射
void CountSort(vector<int>& v)
{
    int n = v.size();
    //1.找出数组的最大值
    int maxNum = v[0];
    for(int i = 1;i<n;i++)
        if(v[i] > maxNum) maxNum = v[i];
    //2.每个元素映射到count数组的对应位置
    vector<int> count(maxNum+1,0);//注意要开maxNum+1个空间！
    for(auto& x:v)
        count[x]++;
    //3.将count数组的内容映射回去原数组
    int index = 0;
    for(int i = 0;i<=maxNum;i++) //注意:i<=maxNum
    {
        while(count[i] > 0)//元素i的出现次数为count[i]
        {
            v[index++] = i;
            count[i]--;//i元素出现次数--,否则死循环
        }
    }
}

//相对映射
void CountSort(vector<int>& v)
{
    int n = v.size();
    //1.找出数组的最大值
    int maxNum = v[0];
    int minNum = v[0];
    for(int i = 1;i<n;i++)
    {
        if(v[i] > maxNum) maxNum = v[i];
        if(v[i] < minNum) minNum = v[i];
    }
    int range = maxNum - minNum + 1;//数组元素范围:[minNum,maxNum]
    //2.数组元素进行映射。此时x元素映射在x - minNum位置
    vector<int> count(range,0);
    for(auto& x:v)
        count[x - minNum]++;
    //3.将count数组的内容映射回去原数组,此时对应的值为i + minNum
    int index = 0;
    for(int i = 0;i< range;i++)
    {
        while(count[i] > 0)//元素i的出现次数为count[i]
        {
            v[index++] = i + minNum;
            count[i]--;//i元素出现次数--,否则死循环
        }
    }
}